/*
 * @Author: wwssaabb
 * @Date: 2021-12-14 10:14:13
 * @LastEditTime: 2021-12-14 11:15:54
 * @FilePath: \handwritten-code\algorithm\最大子数组和.js
 */


/* 
给你一个整数数组 nums， 请你找出一个具有最大和的连续子数组（ 子数组最少包含一个元素）， 返回其最大和。
子数组 是数组中的一个连续部分。

示例 1：
输入： nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出： 6
解释： 连续子数组[4, -1, 2, 1] 的和最大， 为 6。

示例 2：
输入： nums = [1]
输出： 1

示例 3：
输入： nums = [5, 4, -1, 7, 8]
输出： 23

来源： 力扣（ LeetCode）
链接： https: //leetcode-cn.com/problems/maximum-subarray
*/

//暴力解法，超时，时间O(n)，空间O(1)
var maxSubArray = function (nums) {
  let max = -Infinity
  for (let i = 0; i < nums.length; i++) {
    let sum = 0
    for (let j = i; j < nums.length; j++) {
      sum += nums[j]
      max = Math.max(sum, max)
    }
  }
  return max
};


//动态规划，时间O(n),空间O(n)
var maxSubArray = function (nums) {
  let dp = [nums[0]],
    max = nums[0]
  for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])
    max = Math.max(max, dp[i])
  }
  return max
}


console.log(maxSubArray([5, 4, -1, 7, 8]))
console.log(maxSubArray([1]))
console.log(maxSubArray([1, -1]))
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))